package org.example.leetcpde;

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;

public class threeSum
        implements IArray {
    @Test
    void run() {
        int[] nums = parse("[0,0,0,0]");

        List<List<Integer>> lists = threeSumV2(nums);
        System.out.println(22);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        List<List<Integer>> res = new ArrayList<>();
        dfs(new ArrayList<>(), res, nums, new boolean[nums.length], 3, 0, map);
        return res;
    }

    void dfs(List<Integer> state,
             List<List<Integer>> res,
             int[] nums,
             boolean[] visited,
             int target,
             int start,
             Map<Integer, Integer> map) {

        if (state.size() == target) {
            int sum = state.stream().mapToInt(Integer::intValue).sum();
            if (sum == 0) {
                res.add(new ArrayList<>(state));
            }
            return;
        }

        Set<Integer> dup = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            int v1 = nums[i];
            if (visited[i]) {
                continue;
            }

            if (dup.contains(v1)) {
                continue;
            }

            dup.add(v1);
            visited[i] = true;
            state.add(v1);

            dfs(state, res, nums, visited, target, i + 1, map);

            visited[i] = false;
            state.remove(state.size() - 1);
        }
    }

    @Test
    void ab() {
        Set<Set<Integer>> sets = new HashSet<>();
        sets.add(Set.of(-1, 0, 1));
        sets.add(Set.of(0, 1, -1));
        System.out.println(sets.size());
    }

    public List<List<Integer>> threeSumV2(int[] nums) {
        Arrays.sort(nums);
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < len - 2; i++) {
            int v1 = nums[i];
            if (i > 0 && v1 == nums[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < len; j++) {
                int v2 = nums[j];
                if (j > i + 1 && v2 == nums[j - 1]) {
                    continue;
                }
                int diff = 0 - v1 - v2;
                Integer k = map.get(diff);
                if (k != null && k > j) {
                    res.add(List.of(v1, v2, diff));
                }
            }
        }

        return res;
    }

    @Test
    void runV3() {
        int[] nums = parse("[0,0,0,0]");
//        int[] nums = parse("[-1,0,1,2,-1,-4]");

        List<List<Integer>> lists = threeSumV3(nums);
        System.out.println(22);
    }

    public List<List<Integer>> threeSumV3(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            int v1 = nums[i];
            if (i > 0 && v1 == nums[i - 1]) {
                continue;
            }

            for (int j = i + 1, k = len - 1; j < k; ) {
                int v2 = nums[j];
                if (j > i + 1 && v2 == nums[j - 1]) {
                    j++;
                    continue;
                }
                int v3 = nums[k];
                int sum = v1 + v2 + v3;
                if (sum > 0) {
                    k--;
                } else if (sum < 0) {
                    j++;
                } else {
                    res.add(List.of(v1, v2, v3));
                    j++;
                }
            }
        }

        return res;
    }
}
